P6218 [USACO06NOV] Round Numbers S

首先有个想法,如果该位为 00 且不是前导 00,则将 00 的数量加一,最后看 00 是否出现了至少 len2\lceil \frac{\text{len}}{2} \rceil 次。

但这样有个问题,比如在 n=8(1000)2n=8(1000)_2 时, 2(0010)2(0010) 就不会被计入答案 ,原因是 22 的前导 00 也算在了它二进制的位数中。

所以还要记录前导零的数量 leadnum\text{leadnum},最后判断是否出现至少 lenleadnum2\lceil \frac{\text{len}-\text{leadnum}}{2} \rceil 即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int MAXN = 35;
int a[ MAXN + 5 ] , len , dp[ MAXN + 5 ][ MAXN + 5 ][ MAXN + 5 ];

int dfs( int pos , int lead , int leadnum , int limit , int sum ) {
	if( pos == len + 1 ) return sum >= len - leadnum - sum;
	if( ~dp[ pos ][ sum ][ leadnum ] && !lead && !limit ) return dp[ pos ][ sum ][ leadnum ];
    
	int Ans = 0 , Mbit = limit ? a[ len - pos + 1 ] : 1;
	for( int i = 0 ; i <= Mbit ; i ++ ) {
              if( lead && i == 0 ) Ans += dfs( pos + 1 , 1 , leadnum + 1 , limit & ( i == Mbit ) , sum );
              else                 Ans += dfs( pos + 1 , 0 , leadnum , limit & ( i == Mbit ) , sum + ( i == 0 ) );
        }
	if( !lead && !limit ) dp[ pos ][ sum ][ leadnum ] = Ans;
	return Ans;
}
int Solve( int x ) {
	len = 0; for( ; x ; x /= 2 ) a[ ++ len ] = x % 2;
	memset( dp , -1 , sizeof( dp ) );
	return dfs( 1 , 1 , 0 , 1 , 0 );
}

int l , r;
int main( ) {
	scanf("%d %d",&l,&r);
	printf("%d\n", Solve( r ) - Solve( l - 1 ) );
	return 0;
}